import java.util.Arrays;

public class Text1 {
    //两数之和（排序+折半查找）
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        int[] resVal = new int[2];
        int[] copiedNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nums);
        int n1 = -1;
        for (int i = 0; i < nums.length; i++) {
            resVal[0] = nums[i];
            resVal[1] = target - resVal[0];

            n1 = binarySearchBasic(nums, i + 1, resVal[1]);
            if(n1 != -1) {
                break;
            }
        }
        if(n1 == -1) {
            return new int[] {};
        }
        for (int j = 0; j < copiedNums.length; j++) {
            if(copiedNums[j] == resVal[0]) {
                res[0] = j;
                break;
            }
        }
        for (int k = 0; k < copiedNums.length; k++) {

            if(copiedNums[k] == resVal[1] && k != res[0]) {
                res[1] = k;
                break;
            }
        }
        return res;
    }

    public int binarySearchBasic(int[] arr, int low, int target) {
        int high = arr.length - 1;
        while(low <= high) {
            int center = (low + high) / 2;
            if(target == arr[center]) {
                return center;
            }
            else if(target < arr[center]) {
                high = center - 1;
            }
            else {
                low = center + 1;
            }
        }
        return -1;
    }
}